﻿// 4-18.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <math.h>
#include "stack"
#include "vector"
#include "../2-34-Bitmap/Bitmap.h"
using namespace std;


///一些实验用的全局变量
int countGre = 0;

/// <summary>
/// 求一个数的平方根
/// 此法所得为平方根之上整
/// </summary>
/// <param name="n"></param>
/// <param name="k"></param>
/// <returns></returns>
int countSquare(int n, int k=0) {
    return (n < 1) ? k : countSquare(n - 2 * k - 1, k + 1);
}

/// <summary>
/// 求一个数的平方根
/// 此法所得为平方根之下整
/// </summary>
/// <param name="n">只需提供待求的目标数</param>
/// <param name="s">函数自用，用户无需提供，计算此时之上限</param>
/// <param name="k">函数自用，用户无需提供，计数器</param>
/// <returns></returns>
int countSquareDown(int n, int s=0, int k=0) {
    return (n < s) ? k - 1 : countSquareDown(n, s + 2 * k + 1, k + 1);
}

/// <summary>
/// 将栈内各个元素平方后，求和
/// </summary>
/// <param name="st"></param>
/// <returns></returns>
int countStack(stack<int> st) {
    int sum = 0;
    int m = 0;
    while (st.size() != 0) {
        m = st.top();
        sum += m * m;
        st.pop();
    }
    return sum;
}

/// <summary>
/// 求一个栈内，元素总和
/// </summary>
/// <param name="st"></param>
/// <returns></returns>
int coutStackSum(stack<int> st) {
    int sum = 0;
    while (!st.empty()) {
        sum += st.top();
        st.pop();
    }
    return sum;

}



/// <summary>
/// 实时输出栈内元素情况
/// </summary>
/// <param name="st"></param>
void coutStack(stack<int> st) {
    stack<int> ts;
    while (st.size() != 0) {
        ts.push(st.top());
        st.pop();
    }
    while (ts.size() != 0)
    {
        std::cout << ts.top() << " ";
        ts.pop();
    }
    std::cout << "\n";

}

/// <summary>
/// 将栈中的解转移至向量中
/// 转移进来时去一下重
/// 同一组数的不同排列视作等同
/// </summary>
/// <param name="aS"></param>
/// <param name="bV"></param>
void convey(stack<int> aS, vector<int>& bV, Bitmap& M) {
    vector<int> item;
    int n = 0;
    int stSize = aS.size();
    int sum = coutStackSum(aS);
    if (M.test(sum)) return;  //去重
    if (stSize != 4) {
        for (int i = 0; i < 4 - stSize; i++) {
            aS.push(0);
        }
    }
    for (int i = 0; i < 4; i++) {
        n = aS.top();
        item.push_back(n);
        aS.pop();
    }
    for (int i = 3; -1 < i; i--) {
        bV.push_back(item[i]);
    }
    bV.push_back(sum);
    M.set(sum);
}
/// <summary>
/// 输出向量中的费马解
/// </summary>
/// <param name="re"></param>
void coutVector(vector<int> re) {
    int n = 0;  //计数
    for (int i = 0; i < re.size(); i += 5) {
        for (int j = i; j < i+4; j++) {
            std::cout << re[j] << " ";
        }
        n++;
        std::cout << "\n";
    }
    std::cout << "解总计：" << n << "个\n";

}

/// <summary>
/// 对三个辅助位图进行初始化
/// </summary>
/// <param name="M1"></param>
/// <param name="M2"></param>
/// <param name="M3"></param>
/// <param name="numBase"></param>
void setBitmap(Bitmap &M1, Bitmap& M2, Bitmap& M3, int numBase) {

  /*  vector<int> v1;*/
    /*vector<int> v2(3* numBase*numBase);*/
 /*   vector<int> v3;*/
   /* int t = 3 * numBase * numBase;*/
    //int squa = 0;
    //int size = 0;
    //for (int i = 0; i <= numBase; i++) {
    //    squa = i * i;
    //    v1.push_back(squa);
    //}
    /*size = v1.size();*/
    int a = 0;
    int b = 0;
    int c = 0;
    for (int i = 0; i < numBase; i++) {       
        a = i * i;
        M1.set(a);
        for (int j = 0; j < numBase; j++) {
            b = a + j * j;
            M2.set(b);
            for (int k = 0; k < numBase; k++) {
                
                c = b+ k * k;
                M3.set(c);
                /*v2[c] = 1;*/
            }
        }
    }
    int w = 0;

}

/// <summary>
/// a)对任一自然数，找出一个费马拉格朗日分解
/// 0亦是整数
/// 试探回溯，关键都在这两词语了
/// 何为准确的试探
/// 何时应该回溯
/// 我该往下一个走了
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
stack<int> fermatA(int n) {
    stack<int> fer;
    int nn = 0;  //栈中此时所有数字平方数的总和
    int m = 0;  //每一个单元数
    while (n != countStack(fer) || fer.size() < 4) {
        if (fer.size() >= 4 || countStack(fer) > n) {  
            if (countStack(fer) > n) {
                fer.pop();
                m = ++fer.top();
                fer.pop();
            }
            else {
                m = ++fer.top();
                fer.pop();
            }
            
        }
        else {  
            fer.push(m);
            m = 0;
        }
        int fsize = fer.size();
        int nn = countStack(fer);
        coutStack(fer);
    }
    return fer;

}

/// <summary>
/// 优化优化优化
/// 剪枝
/// </summary>
/// <param name="st"></param>
/// <param name="m"></param>
/// <param name="mMax"></param>
/// <param name="M"></param>
/// <param name="n"></param>
/// <returns></returns>
int optimazation(stack<int> st, int m, int mMax, Bitmap& M, Bitmap& N1,Bitmap& N2,Bitmap& N3,int n) {
    int nn = countStack(st);
    int size = st.size();
    int sum = coutStackSum(st);
    int nextNn = nn + m * m;  //若加入目前之m后，整体之值
    
    if (nn > n || nextNn > n) {
        m = mMax;
        countGre++;  //计数

    }
    else {
        if (size == 0) {
            while (m < mMax)
            {
               // try {
               //     if (N3.test(n - m * m))break;
               //}
               // catch (exception) {
               //     int p = m;
               // }
                if (N3.test(n - m * m))break;
                m++;
            }
        }
        if (size == 1) {
            while (m < mMax)
            {
                //try {
                //    if ((n - (nn + m * m)) < 0) {
                //        m = mMax;
                //        break;
                //    }
                //    if (N2.test(n - (nn + m * m)))break;
                //}
                //catch (exception) {
                //    int p = m;
                //}
                if ((n - (nn + m * m)) < 0) {
                    m = mMax;
                    break;
                }
                if (N2.test(n - (nn + m * m)))break;
                m++;
            }
        }
        if (size == 2) {
            while (m < mMax)
            {
                //try {
                //    if ((n - (nn + m * m)) < 0) {
                //        m = mMax;
                //        break;
                //    }
                //    if (N1.test(n - (nn + m * m)))break;
                //}
                //catch (exception) {
                //    int p = m;
                //}
                if ((n - (nn + m * m)) < 0) {
                    m = mMax;
                    break;
                }
                if (N1.test(n - (nn + m * m)))break;
                m++;
            }
        }
        if (size == 3) {
            while (m < mMax)
            {
                if (nn + m * m == n) break;
                m++;
            }
            if (M.test(sum + m)) m = mMax;
        }
    }
    return m;
}

/// <summary>
/// b)对任一自然数，找出所有费马-拉格朗日分解（同一组数的不同排列视作等同）
/// 找完后用一个向量返回去
/// 问题1，如何筛掉同一组数的不同排列呢？
/// 找完后筛（自然落了下乘）
/// 找的时候筛？（自是上乘，但无头绪呀）
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
vector<int> fermatB(int n) {
    stack<int> fer;  //回溯道具
    vector<int> reVector;
    int nn = 0;  //栈中此时所有数字平方数的总和
    int m = 0;  //每一个单元数
    int mMax = countSquareDown(n) + 1;  //找出严格不能达到的上界
                                        //此时所有至上界者都必然不是解，所以，元素不可至上界
                                        // 我已然断定，此不为解
    int squaN = mMax * mMax;
    ///辅助工具出手
    Bitmap M(n);  //和
    Bitmap BN1(squaN);  //一个数所能成之平方
    Bitmap BN2(2*squaN);  //两个数所能成之平方
    Bitmap BN3(3*squaN);  //三个数所能成之平方

    setBitmap(BN1, BN2, BN3, mMax);  //对三个辅助数位图初始化

    ///将所有的
    //此刻的循环，何时方止住呢？
    //穷举完成之时，八皇后的穷举完成之时在(0,N)坐标之时，
    //我的在，只用一个元素时，且m达到了上界，则已穷举完成（不，你错了，你只有在size为0时，你才能拿到序号0元素作为m
    while (0 <fer.size() || m < mMax) {
        if (fer.size() >= 4 || m >= mMax) {

                m = ++fer.top();
                fer.pop();

        }
        else {
            m = optimazation(fer, m, mMax, M,BN1,BN2,BN3,n);
            if (m < mMax) {
                fer.push(m);
                if (countStack(fer) == n) {
                    convey(fer, reVector,M);
                }
                m = 0;
            }
        }
        //int fsize = fer.size();
        //int nn = countStack(fer);
        /*coutStack(fer);*/
    }
    return reVector;

}

/// <summary>
/// 计算一个数的所有费马-拉格朗日分解
/// 循环迭代版
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
vector<int> fermatM(int n) {
    int mMax = countSquareDown(n) + 1;  //所有的边界，不可达到之处
    vector<int> re;
    bool isRepeat = false;
    int sum = 0;
    for (int i = 0; i < mMax; i++) {
        for (int j = 0; j < mMax; j++) {
            for (int k = 0; k < mMax; k++) {
                for (int w = 0; w < mMax; w++) {
                    if (i * i + j * j + k * k + w * w == n) {
                        sum = i + j + k + w;
                        if (!re.empty()) {
                            for (int q = 4; q < re.size(); q += 5) {
                                if (re[q] == sum) {
                                    isRepeat = true;
                                    break;
                                }     
                            }
                            if (isRepeat) {
                                isRepeat = false;
                                continue;
                            }
                        }
                        re.push_back(i);
                        re.push_back(j);
                        re.push_back(k);
                        re.push_back(w);
                        re.push_back(sum);
                    }
                }
            }
        }
    }
    return re;
}

int main()
{
    int n = 9999999;
    std::cout << "Hello World!\n";
    //stack<int> fer = fermatA(30);
    //std::cout << countSquare(12);
    vector<int> reVecor = fermatB(n);
   /* vector<int> reVecor = fermatM(3304);*/
    coutVector(reVecor);
    std::cout << "解总计：" << reVecor.size() / 5 << "个\n";
    std::cout << "可优化次数：" << countGre<< "次\n";

}




// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
